Crate kiddo

source ·
Expand description

Kiddo

A high-performance, flexible, ergonomic k-d tree library.

Possibly the fastest k-d tree library in the world? See for yourself.

Version 2.x is a complete rewrite, providing:

  • a new internal architecture for much-improved performance;
  • Added integer / fixed point support via the Fixed library;
  • instant zero-copy deserialization and serialization via Rkyv (Serde still available).
  • See the changelog for a detailed run-down on all the changes made in v2.

Kiddo is ideal for super-fast spatial / geospatial lookups and nearest-neighbour / KNN queries for low-ish numbers of dimensions, where you want to ask questions such as:

  • Find the nearest_n item(s) to a query point, ordered by distance;
  • Find all items within a specified radius of a query point;
  • Find the “best” n item(s) within a specified distance of a query point, for some definition of “best”

Installation

Add kiddo to Cargo.toml

[dependencies]
kiddo = "2.1.2"

Usage

use kiddo::KdTree;
use kiddo::distance::squared_euclidean;
use kiddo::float::neighbour::Neighbour;

let entries = vec![
    [0f64, 0f64],
    [1f64, 1f64],
    [2f64, 2f64],
    [3f64, 3f64]
];

// use the kiddo::KdTree type to get up and running quickly with default settings
let mut kdtree: KdTree<_, 2> = (&entries).into();

// How many items are in tree?
assert_eq!(kdtree.size(), 4);

// find the nearest item to [0f64, 0f64].
// returns a tuple of (dist, index)
assert_eq!(
    kdtree.nearest_one(&[0f64, 0f64], &squared_euclidean),
    (0f64, 0)
);

// find the nearest 3 items to [0f64, 0f64], and collect into a `Vec`
assert_eq!(
    kdtree.nearest_n(&[0f64, 0f64], 3, &squared_euclidean),
    vec![Neighbour { distance: 0f64, item: 0 }, Neighbour { distance: 2f64, item: 1 }, Neighbour { distance: 8f64, item: 2 }]
);

See the examples documentation for some more in-depth examples.

Modules

  • distance
    Some experimental distance metrics work
  • fixed
    Fixed point k-d tree, for use when the co-ordinates of the points being stored in the tree are fixed point or integers. u8, u16, u32, and u64 based fixed-point / integers are supported via the Fixed crate, eg FixedU16<U14> for a 16-bit fixed point number with 14 bits after the decimal point.
  • float
    Floating point k-d tree, for use when the co-ordinates of the points being stored in the tree are floats. f64 or f32 are the types that are supported for use as co-ordinates.
  • types
    Definitions for some types that are common between the fixed and float modules

Macros

Type Aliases

  • KdTree
    A floating-point k-d tree with default parameters.